#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <pthread.h>
#include <errno.h>

#include "../common/logger.h"

/*
Implement a set of thread-safe functions that update and search an unbalanced
binary tree. This library should include functions (with the obvious purposes) of
the following form:
initialize(tree);
add(tree, char *key, void *value);
delete(tree, char *key)
Boolean lookup(char *key, void **value)
In the above prototypes, tree is a structure that points to the root of the tree (you
will need to define a suitable structure for this purpose). Each element of the tree
holds a key-value pair. You will also need to define the structure for each element
to include a mutex that protects that element so that only one thread at a time can
access it. The initialize(), add(), and lookup() functions are relatively simple to imple-
ment. The delete() operation requires a little more effort.
Removing the need to maintain a balanced tree greatly simplifies the locking
requirements of the implementation, but carries the risk that certain patterns
of input would result in a tree that performs poorly. Maintaining a balanced
tree necessitates moving nodes between subtrees during the add() and delete()
operations, which requires much more complex locking strategies.
 */

struct node {
        struct node *left;
        char *key;
        void *data;
        struct node *right;
};

struct tree {
        struct node *root;
        pthread_mutex_t mutex;
};

void initialize(struct tree *tree)
{
        tree->root = NULL;
        pthread_mutex_init(&tree->mutex, NULL);
}

void deinit(struct tree **tree)
{
        pthread_mutex_destroy(&(*tree)->mutex);
        *tree = NULL;
}

void add(struct tree *tree, char *key, void *data)
{
        pthread_mutex_lock(&tree->mutex);
        struct node **next = &tree->root;
        while (*next != NULL) {
                int ret = strcmp((*next)->key, key);
                if (ret > 0)
                        next = &(*next)->right;
                else if (ret < 0)
                        next = &(*next)->left;
                else
                        goto key_already_exist;
        }

        *next = malloc(sizeof(**next));
        (*next)->key = strdup(key);
        (*next)->data = data;
        (*next)->left = NULL;
        (*next)->right = NULL;
        goto out;

 key_already_exist:
        warnx("key %s already exist in tree", key);
 out:
        pthread_mutex_unlock(&tree->mutex);
}

void delete(struct tree *tree, char *key)
{
        pthread_mutex_lock(&tree->mutex);
        struct node **next = &tree->root;
        while (*next != NULL) {
                int ret = strcmp((*next)->key, key);
                if (ret > 0)
                        next = &(*next)->right;
                else if (ret < 0)
                        next = &(*next)->left;
                else {
                        struct node *to_delete = *next;
                        if ((*next)->right)
                                *next = (*next)->right;
                        else
                                *next = (*next)->left;

                        free(to_delete->key);
                        free(to_delete);
                }
        }
        pthread_mutex_unlock(&tree->mutex);
}

bool lookup(struct tree *tree, char *key, void **data)
{
        pthread_mutex_lock(&tree->mutex);
        struct node *next = tree->root;
        while (next != NULL) {
                int ret = strcmp(next->key, key);
                if (ret > 0)
                        next = next->right;
                else if (ret < 0)
                        next = next->left;
                else {
                        *data = next->data;
                        return true;
                }
        }
        pthread_mutex_unlock(&tree->mutex);

        return false;
}

void print_tree(struct tree *tree)
{
        void print_tree_aux(struct node *node)
        {
                if (node == NULL) return;
                printf("%s :: %p\n", node->key, node->data);
                print_tree_aux(node->left);
                print_tree_aux(node->right);
        }
        puts("printing tree");
        print_tree_aux(tree->root);
}

int main(void) {
        struct tree tree;
        initialize(&tree);
        add(&tree, "daniel", (void *)2);
        print_tree(&tree);
        add(&tree, "joanna", (void *)3);
        print_tree(&tree);
        delete(&tree, "daniel");
        print_tree(&tree);

        void *var = NULL;
        if (lookup(&tree, "joanna", &var))
                printf("found: %p\n", var);
        return EXIT_SUCCESS;
}
